package com.njupt.DynamicProgramming;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/7 8:58
 * @Description: 474. 一和零  本质是两个维度的背包
 * 至多包含m个0 和n个1，相当于有一个背包背包的容量为m+n，最多m个0和n个1，这里背包的维度有两维
 * 这个求最大子集的个数，我们可以将数组中每个元素看成一个物品，每个物品的重量为x个0和y个1
 *
 * 1、dp数组的含义
 * 一般求说明dp数组设置为什么，所以这里dp数组的含义是dp[i][j]背包中有i个0和j个1时所能装下的最大物品个数
 * 2、递推公式
 * dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1)
 *
 * 3、dp初始化
 *
 * 4、遍历顺序
 * @Version: 1.0
 */


public class FindMaxForm_474 {


    public int findMaxForm(String[] strs, int m, int n) {
        //1、法一回溯法。超时
//        int startIndex = 0;
//        List<List<String>> results = new ArrayList<>();
//        List<String> result = new LinkedList<>();
//        trackBacking(startIndex,strs,m,n,results,result);
//        int maxLen = Integer.MIN_VALUE;
//        for (List<String> strings : results) {
//            System.out.println(strings);
//            if(strings.size()>maxLen){
//                maxLen = strings.size();
//            }
//        }
//        return maxLen == Integer.MIN_VALUE?0:maxLen;

        //2、法二、动态规划
        int[][] dp = new int[m+1][n+1];
        for (String str : strs) {  //遍历物品
            int x = 0;  //统计0的个数
            int y = 0;  //统计1的个数
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if(c == '0'){
                    x++;
                }else {
                    y++;
                }
            }
            //遍历背包
            for (int i = m; i >= x ; i--) {
                for (int j = n; j >= y ; j--) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y] + 1);
                }
            }
        }
        return dp[m][n];


    }

    /**
     * 回溯法
     * @param startIndex
     * @param strs
     * @param m
     * @param n
     * @param results
     * @param result
     */
    private void trackBacking(int startIndex, String[] strs, int m, int n, List<List<String>> results, List<String> result) {

        //TODO 1、递归结束的条件
        int mNumber = 0;
        int nNumber = 0;
        for (int i = 0; i < result.size(); i++) {
            String s = result.get(i);
            for (int j = 0; j < s.length(); j++) {
                if(s.charAt(j) == '1'){
                    nNumber++;
                }else {
                    mNumber++;
                }
            }
        }
        if( (m >= mNumber && mNumber>0) && (n >= nNumber && nNumber > 0)){
            results.add(new ArrayList<>(result));
//            return;
        }
        if(n < nNumber || m < mNumber){
            return;
        }

        for (int i = startIndex; i < strs.length; i++) {
            String str = strs[i];
            result.add(str);
            trackBacking(i+1,strs,m,n,results,result);
            result.remove(result.size()-1); //回溯
        }
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
//        String[] strs = {"10", "0", "1"};
//        String[] strs = {"10001110","11000","111110"};
        FindMaxForm_474 test = new FindMaxForm_474();
        int maxForm = test.findMaxForm(strs, 5, 3);
        System.out.println(maxForm);

    }
}
